#leetcode题目322：零钱兑换
#难度：中等
#时间复杂度：O(n)
#空间复杂度：O(n)
#方法：动态规划

#题目理解：
# 类似于背包问题，一个固定容量的背包，装满这个背包，最少需要多少个物品。
#简化成：当前选择的数字，当前剩余的空间。

from typing import List
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        """
        零钱兑换
        给定不同面额的硬币 coins 和一个总金额 amount。
        编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
        如果没有任何一种硬币组合能组成总金额，返回 -1。
        """
        # 边界情况：没有硬币
        if not coins:
            return -1
        
        # 初始化记忆化数组，0表示未计算
        dp = [0] * (amount + 1)
        
        return self.process(coins, amount, dp)

    def process(self, coins: List[int], amount: int, dp: List[int]) -> int:
        """
        递归处理函数 - 记忆化搜索
        :param coins: 硬币面额数组
        :param amount: 目标金额
        :param dp: 记忆化数组
        :return: 最少硬币数量，-1表示无解
        """
        # 基础情况1：金额为负数，无效
        if amount < 0:
            return -1
        
        # 记忆化检查：如果已经计算过，直接返回
        if dp[amount] != 0:
            return dp[amount]
        
        # 基础情况2：金额为0，不需要硬币
        if amount == 0:
            return 0
        
        res = float('inf')
        
        # 尝试每种硬币
        for coin in coins:
            # 如果当前硬币面额大于剩余金额，跳过
            if coin <= amount:
                # 递归计算使用当前硬币后的最少硬币数
                sub_result = self.process(coins, amount - coin, dp)
                
                # 如果子问题有解，更新结果
                if sub_result != -1:
                    res = min(res, sub_result + 1)
        
        # 如果没有找到解，设为-1，否则设为找到的最小值
        dp[amount] = -1 if res == float('inf') else res
        return dp[amount]





#测试数据
coins = [1, 2, 5]
amount = 11
#预期输出：3，11=5+5+1
solution = Solution()
print(solution.coinChange(coins, amount))

coins = [2]
amount = 3
#预期输出：-1，无法凑成3
solution = Solution()
print(solution.coinChange(coins, amount))